#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dijkstra(vector<vector<vector<int>>> &gh, int s)
{
        int n = gh.size() - 1;
        vector<int> vis(n + 1, 0);
        vector<int> dis(n + 1, INT32_MAX);
        priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<>> pq;

        int ans = 0, cnt = 0;
        dis[s] = 0;
        pq.emplace(0, s);
        while(!pq.empty()){
                auto [t, u] = pq.top();
                pq.pop();
                if(vis[u]){
                        continue;
                }
                vis[u] = 1;
                ans = max(ans, dis[u]);
                cnt++;

                for(auto e : gh[u]){
                        int v = e[0], c = e[1];
                        if(!vis[v] && t + c < dis[v]){
                                dis[v] = t + c;
                                pq.emplace(dis[v], v);  
                        }
                }
        }
        return cnt == n ? ans : -1;
}

int main()
{
        int n, m;
        cin >> n >> m;
        vector<vector<vector<int>>> gh(n + 1);
        vector<int> vis(n + 1, 0);
        for(int i = 0; i < m; i++){
                int u, v, t;
                cin >> u >> v >> t;
                gh[u].push_back({v, t});
                gh[v].push_back({u, t});
        }
        cout<<dijkstra(gh, 1)<<endl;
        return 0;
}

